// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "leveldb/cache.h"

#include <vector>

#include "gtest/gtest.h"
#include "util/coding.h"

namespace leveldb
{

    // Conversions between numeric keys/values and the types expected by Cache.
    static std::string EncodeKey(int k)
    {
        std::string result;
        PutFixed32(&result, k);
        return result;
    }
    static int DecodeKey(const Slice &k)
    {
        assert(k.size() == 4);
        return DecodeFixed32(k.data());
    }
    static void *EncodeValue(uintptr_t v) { return reinterpret_cast<void *>(v); }
    static int DecodeValue(void *v) { return reinterpret_cast<uintptr_t>(v); }

    class CacheTest : public testing::Test
    {
    public:
        static void Deleter(const Slice &key, void *v)
        {
            current_->deleted_keys_.push_back(DecodeKey(key));
            current_->deleted_values_.push_back(DecodeValue(v));
        }

        static constexpr int kCacheSize = 1000;
        std::vector<int> deleted_keys_;
        std::vector<int> deleted_values_;
        Cache *cache_;

        CacheTest() : cache_(NewLRUCache(kCacheSize)) { current_ = this; }

        ~CacheTest() { delete cache_; }

        int Lookup(int key)
        {
            Cache::Handle *handle = cache_->Lookup(EncodeKey(key));
            const int r = (handle == nullptr) ? -1 : DecodeValue(cache_->Value(handle));
            if (handle != nullptr)
            {
                cache_->Release(handle);
            }
            return r;
        }

        void Insert(int key, int value, int charge = 1)
        {
            cache_->Release(cache_->Insert(EncodeKey(key), EncodeValue(value), charge,
                                           &CacheTest::Deleter));
        }

        Cache::Handle *InsertAndReturnHandle(int key, int value, int charge = 1)
        {
            return cache_->Insert(EncodeKey(key), EncodeValue(value), charge,
                                  &CacheTest::Deleter);
        }

        void Erase(int key) { cache_->Erase(EncodeKey(key)); }
        static CacheTest *current_;
    };
    CacheTest *CacheTest::current_;

    TEST_F(CacheTest, HitAndMiss)
    {
        ASSERT_EQ(-1, Lookup(100));

        Insert(100, 101);
        ASSERT_EQ(101, Lookup(100));
        ASSERT_EQ(-1, Lookup(200));
        ASSERT_EQ(-1, Lookup(300));

        Insert(200, 201);
        ASSERT_EQ(101, Lookup(100));
        ASSERT_EQ(201, Lookup(200));
        ASSERT_EQ(-1, Lookup(300));

        Insert(100, 102);
        ASSERT_EQ(102, Lookup(100));
        ASSERT_EQ(201, Lookup(200));
        ASSERT_EQ(-1, Lookup(300));

        ASSERT_EQ(1, deleted_keys_.size());
        ASSERT_EQ(100, deleted_keys_[0]);
        ASSERT_EQ(101, deleted_values_[0]);
    }

    TEST_F(CacheTest, Erase)
    {
        Erase(200);
        ASSERT_EQ(0, deleted_keys_.size());

        Insert(100, 101);
        Insert(200, 201);
        Erase(100);
        ASSERT_EQ(-1, Lookup(100));
        ASSERT_EQ(201, Lookup(200));
        ASSERT_EQ(1, deleted_keys_.size());
        ASSERT_EQ(100, deleted_keys_[0]);
        ASSERT_EQ(101, deleted_values_[0]);

        Erase(100);
        ASSERT_EQ(-1, Lookup(100));
        ASSERT_EQ(201, Lookup(200));
        ASSERT_EQ(1, deleted_keys_.size());
    }

    TEST_F(CacheTest, EntriesArePinned)
    {
        Insert(100, 101);
        Cache::Handle *h1 = cache_->Lookup(EncodeKey(100));
        ASSERT_EQ(101, DecodeValue(cache_->Value(h1)));

        Insert(100, 102);
        Cache::Handle *h2 = cache_->Lookup(EncodeKey(100));
        ASSERT_EQ(102, DecodeValue(cache_->Value(h2)));
        ASSERT_EQ(0, deleted_keys_.size());

        cache_->Release(h1);
        ASSERT_EQ(1, deleted_keys_.size());
        ASSERT_EQ(100, deleted_keys_[0]);
        ASSERT_EQ(101, deleted_values_[0]);

        Erase(100);
        ASSERT_EQ(-1, Lookup(100));
        ASSERT_EQ(1, deleted_keys_.size());

        cache_->Release(h2);
        ASSERT_EQ(2, deleted_keys_.size());
        ASSERT_EQ(100, deleted_keys_[1]);
        ASSERT_EQ(102, deleted_values_[1]);
    }

    TEST_F(CacheTest, EvictionPolicy)
    {
        Insert(100, 101);
        Insert(200, 201);
        Insert(300, 301);
        Cache::Handle *h = cache_->Lookup(EncodeKey(300));

        // Frequently used entry must be kept around,
        // as must things that are still in use.
        for (int i = 0; i < kCacheSize + 100; i++)
        {
            Insert(1000 + i, 2000 + i);
            ASSERT_EQ(2000 + i, Lookup(1000 + i));
            ASSERT_EQ(101, Lookup(100));
        }
        ASSERT_EQ(101, Lookup(100));
        ASSERT_EQ(-1, Lookup(200));
        ASSERT_EQ(301, Lookup(300));
        cache_->Release(h);
    }

    TEST_F(CacheTest, UseExceedsCacheSize)
    {
        // Overfill the cache, keeping handles on all inserted entries.
        std::vector<Cache::Handle *> h;
        for (int i = 0; i < kCacheSize + 100; i++)
        {
            h.push_back(InsertAndReturnHandle(1000 + i, 2000 + i));
        }

        // Check that all the entries can be found in the cache.
        for (int i = 0; i < h.size(); i++)
        {
            ASSERT_EQ(2000 + i, Lookup(1000 + i));
        }

        for (int i = 0; i < h.size(); i++)
        {
            cache_->Release(h[i]);
        }
    }

    TEST_F(CacheTest, HeavyEntries)
    {
        // Add a bunch of light and heavy entries and then count the combined
        // size of items still in the cache, which must be approximately the
        // same as the total capacity.
        const int kLight = 1;
        const int kHeavy = 10;
        int added = 0;
        int index = 0;
        while (added < 2 * kCacheSize)
        {
            const int weight = (index & 1) ? kLight : kHeavy;
            Insert(index, 1000 + index, weight);
            added += weight;
            index++;
        }

        int cached_weight = 0;
        for (int i = 0; i < index; i++)
        {
            const int weight = (i & 1 ? kLight : kHeavy);
            int r = Lookup(i);
            if (r >= 0)
            {
                cached_weight += weight;
                ASSERT_EQ(1000 + i, r);
            }
        }
        ASSERT_LE(cached_weight, kCacheSize + kCacheSize / 10);
    }

    TEST_F(CacheTest, NewId)
    {
        uint64_t a = cache_->NewId();
        uint64_t b = cache_->NewId();
        ASSERT_NE(a, b);
    }

    TEST_F(CacheTest, Prune)
    {
        Insert(1, 100);
        Insert(2, 200);

        Cache::Handle *handle = cache_->Lookup(EncodeKey(1));
        ASSERT_TRUE(handle);
        cache_->Prune();
        cache_->Release(handle);

        ASSERT_EQ(100, Lookup(1));
        ASSERT_EQ(-1, Lookup(2));
    }

    TEST_F(CacheTest, ZeroSizeCache)
    {
        delete cache_;
        cache_ = NewLRUCache(0);

        Insert(1, 100);
        ASSERT_EQ(-1, Lookup(1));
    }

} // namespace leveldb

int main(int argc, char **argv)
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
